package com.shm.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 1189. “气球” 的最大数量
 * 给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 "balloon"（气球）。
 *
 * 字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 "balloon"。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：text = "nlaebolko"
 * 输出：1
 * 示例 2：
 *
 *
 *
 * 输入：text = "loonbalxballpoon"
 * 输出：2
 * 示例 3：
 *
 * 输入：text = "leetcode"
 * 输出：0
 *
 *
 * 提示：
 *
 * 1 <= text.length <= 10^4
 * text 全部由小写英文字母组成
 * @author SHM
 */
public class MaxNumberOfBalloons {
    public int maxNumberOfBalloons(String text) {
        String balloon = "balloon";
        Map<Character,Integer> map = new HashMap<>(5);
        for (char c : balloon.toCharArray()) {
            map.put(c,0);
        }
        for (char c : text.toCharArray()) {
            if (c=='b'||c=='a'||c=='l'||c=='o'||c=='n'){
                map.put(c,map.get(c)+1);
            }
        }
        int ans = Integer.MAX_VALUE;
        for (Character character : map.keySet()) {
            Integer temp = map.get(character);
            if (character=='l'||character=='o'){
                temp/=2;
            }
            if (temp<ans){
                ans=temp;
            }
        }

        return ans;
    }

    /**
     * 方法一：统计
     * 思路
     *
     * 构成单词 \texttt{"balloon"}"balloon" 需要 11 个字母 \texttt{`b'}‘b’ 、11 个字母 \texttt{`a'}‘a’ 、22 个字母 \texttt{`l'}‘l’ 、22 个字母 \texttt{`o'}‘o’ 、11 个字母 \texttt{`n'}‘n’，因此只需要统计字符串中字母 \texttt{`a',`b',`l',`o',`n'}‘a’,‘b’,‘l’,‘o’,‘n’ 的数量即可。其中每个字母 \texttt{"balloon"}"balloon" 需要两个 \texttt{`l',`o'}‘l’,‘o’，可以将字母 \texttt{`l',`o'}‘l’,‘o’ 的数量除以 22，返回字母 \texttt{`a',`b',`l',`o',`n'}‘a’,‘b’,‘l’,‘o’,‘n’ 中数量最小值即为可以构成的单词数量。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n + C)O(n+C)，其中 nn 为字符串的长度，CC 表示单词中字符的种类数，在本题中 C = 5C=5。需要遍历一遍字符串，并求出单词中字符的最小数目。
     *
     * 空间复杂度：O(C)O(C)，CC 表示单词中字符的种类数，在本题中 C = 5C=5。需要 O(C)O(C) 的空间存储字符的统计数目。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/maximum-number-of-balloons/solution/qi-qiu-de-zui-da-shu-liang-by-leetcode-s-nku5/
     * @param text
     * @return
     */
    public int maxNumberOfBalloons_1(String text) {
        int[] cnt = new int[5];
        for (int i = 0; i < text.length(); ++i) {
            char ch = text.charAt(i);
            if (ch == 'b') {
                cnt[0]++;
            } else if (ch == 'a') {
                cnt[1]++;
            } else if (ch == 'l') {
                cnt[2]++;
            } else if (ch == 'o') {
                cnt[3]++;
            } else if (ch == 'n') {
                cnt[4]++;
            }
        }
        cnt[2] /= 2;
        cnt[3] /= 2;
        return Arrays.stream(cnt).min().getAsInt();
    }
}
